An integrated circuit (“IC”) is a device (e.g., a semiconductor device) or electronic system that includes many electronic components, such as transistors, resistors, diodes, etc. These components are often interconnected to form multiple circuit components, such as gates, cells, memory units, arithmetic units, controllers, decoders, etc. An IC includes multiple layers of wiring that interconnect the IC's electronic and circuit components.
Design engineers design ICs by transforming logical or circuit descriptions of the ICs' components into geometric descriptions, called design layouts. Design layouts typically include (1) circuit modules (i.e., geometric representations of electronic or circuit IC components) with pins and (2) interconnect lines (i.e., geometric representations of wiring) that connect the pins of the circuit modules. In this fashion, design layouts often describe the behavioral, architectural, functional, and structural attributes of the IC. To create design layouts, design engineers typically use electronic design automation (“EDA”) applications. These applications provide sets of computer-based tools for creating, editing, analyzing, and verifying design layouts. The applications also render the layouts on a display device or to storage for displaying later.
Fabrication foundries (“fabs”) manufacture ICs based on the design layouts using a photolithographic process. Photolithography is an optical printing and fabrication process by which patterns on a photolithographic mask (i.e., “photomask,” “mask,” or “mask layer”) are imaged and defined onto a photosensitive layer coating a substrate. To fabricate an IC, photomasks are created using the IC design layout as a template. The photomasks contain the various geometries or shapes (i.e., features) of the IC design layout. The various geometries or shapes contained on the photomasks correspond to the various base physical IC elements that comprise functional circuit components such as transistors, interconnect wiring, vertical interconnect access (via) pads, as well as other elements that are not functional circuit elements but are used to facilitate, enhance, or track various manufacturing processes. Through sequential use of the various photomasks corresponding to a given IC in an IC fabrication process, a large number of material layers of various shapes and thicknesses with various conductive and insulating properties may be built up to form the overall IC and the circuits within the IC design layout.
As more circuit features are packed into an IC design layout (e.g., manufacturing processes at feature sizes of 20 nm and below), the resolution of the photolithographic process makes it extremely difficult to fabricate the geometries or shapes on a single lithography mask. The difficulty stems from constraining factors in traditional photolithographic processes that limit the effectiveness of current photolithographic processes. Some such constraining factors are the lights/optics used within the photolithographic processing systems. Specifically, the lights/optics are band limited due to physical limitations (e.g., wavelength and aperture) of the photolithographic process. Therefore, the photolithographic process cannot print beyond a certain minimum width of a feature, minimum spacing between features, and other such physical manufacturing constraints.
For a particular layer of the IC fabrication process, the pitch specifies the sum of the width of a feature and the space on one side of the feature separating that feature from a neighboring feature on the same layer. The minimum pitch for a layer is the sum of the minimum feature width and the minimum spacing between features on the same layer. Depending on the photolithographic process at issue, factors such as optics and wavelengths of light or radiation restrict how small the pitch may be made before features can no longer be reliably printed to a wafer or mask. As such, the smallest size of any features that can be created on a layer of an IC is limited by the minimum pitch for the layer.
FIG. 1 illustrates a typical pitch constraint of a photolithographic process. In FIG. 1, a pitch 110 acts to constrain the spacing between printable features 120 and 130 of a design layout. While other photolithographic process factors such as the threshold 140 can be used to narrow the width 150 of the features 120 and 130, such adjustments do not result in increased feature density without adjustments to the pitch 110. As a result, increasing feature densities beyond a certain threshold is infeasible via a pitch constrained single exposure process.
To enhance the feature density, the shapes on a single layer can be manufactured on two different photolithographic masks. This approach is often referred to as “Double Patterning Lithography (DPL)” technology. FIG. 2 illustrates an example of this approach. In FIG. 2, a design layout 205 specifies three features 210-230 that are pitch constrained and therefore cannot be photo-lithographically printed with a conventional single exposure process. Analysis of the characteristics (e.g., the band limitation) of the available photolithographic process and of the design layout 205 results in the decomposition of the design layout 205 into a first exposure 240 for printing features 210 and 230 and a second exposure 250 for printing feature 220. As such, the features 210 and 230 are assigned to a first photomask for printing during the first exposure 240 and feature 220 is assigned to a second photomask for printing during the second exposure 250.
Some EDA tools model each shape in a design layout as a node in a graph to find conflicts in assigning the shapes to different masks. Two nodes are connected with a link (or a line, an edge, etc.) when the two corresponding shapes are within a threshold distance (e.g., a minimum pitch). The EDA tools also assign the shapes into different masks by assigning different colors to the nodes that represent the shapes. A node in a graph is assigned a color in such a way that the neighboring nodes have different colors. This is because when the neighboring nodes (e.g., a connected pair of nodes) have the same color, the corresponding shapes would violate a design rule (e.g., a pitch requirement). However, when the nodes in a graph form a loop and there are an odd number of nodes in such graph, it is not possible to assign different colors to all pairs of nodes of the graph. Such a loop is referred to as a double patterning (DP) loop or a DP loop violation in this application.
FIG. 3 illustrates a graph 305 that has three nodes that form a DP loop. The graph 305 represents shapes 1-3 in a layer of a design layout 300. This figure illustrates three different color assignments 301-303 to show that it is not possible to assign different colors to adjacent nodes in a graph that has an odd number of nodes forming a loop. Nodes 1-3 of the graph 305 represent the shapes 1-3, respectively. Two different colors, a first color and a second color, are assigned to the shapes 1-3. The first color is depicted as gray and the second color is white in this example. This figure also illustrates a minimum pitch 310 depicted as a horizontal line with two ends having vertical bars. As shown, shape 3 is depicted as three connected rectangles. These three rectangles are connected by design and treated as one shape in this example.
Each pair of shapes in the shapes 1-3 are within the minimum pitch 310. That is, the shapes 1 and 2 are within the minimum pitch; the shapes 1 and 3 are within the minimum pitch; and the shapes 2 and 3 are within the minimum pitch. Accordingly, the nodes 1-3 of the graph 305 are connected to each other, resulting in a loop. The three different colors assignments 301-303 show the three possible ways of assigning two different colors to the nodes 1-3 and the corresponding shapes 1-3. As shown, no matter how the color assignment is done, one pair of neighboring nodes has the same color. That is, there is always going to be a pair of shapes that would be violating the pitch requirement because the two corresponding nodes with the same assigned color are connected.
FIG. 4 illustrates an example printing error that is materialized on the physical wafer when the three shapes 1-3 illustrated in FIG. 3 that are assigned to two different masks get printed. Specifically, this figure shows a possible pattern 430 resulting from applying the color assignment 302 illustrated in FIG. 3. As shown, the shapes 1-3 are divided into two sets of shapes 410 and 415 according to the color assignment 302. That is, the shape 2 is sent to the first of the two masks and the shapes 1 and 3 are sent to the second mask.
Each set of shapes is printed during an exposure of a double exposure photolithographic printing process (e.g., a DPL process). That is, the shape set 410 (i.e., the shape 2) is printed during the first exposure in order to produce contours 420 and the shape set 415 is printed during the second exposure in order to produce contours 425. However, because the shape 1 and the shape 3 were too close (e.g., within the minimum pitch 310), the contour for the shape 1 and the contour for shape 2 intersect and result in a short in this example. The resulting union of the contours 420 and 425 generates the pattern 430. As shown, the pattern 430 did not meet the specifications within the original design layout represented by the pattern 405 in which shapes 1 and 3 are not meant to connect to each other.
In order to avoid printing errors at the fabs, the designers break DP loops in the design layouts before printing. Different designers use different design solutions to break DP loops. For instance, some design solutions break DP loops by moving one or both shapes of a pair of shapes in a DP loop away from each other so that the two shapes are not within the minimum pitch. Therefore, it is important to identify all DP loops existing in the design layouts. However, the existing approaches that identify DP loops often result in incorrectly or falsely identified DP loops or fail to identify DP loops that exist in the layouts.